package com.my.sort;

import java.util.Arrays;
import java.util.Comparator;

/**
 * Created by ZhongGang
 * at 2018/10/10 11:41
 */
public class MinHeap<E> {
    private E[] elements;
    private int size;
    private Comparator<E> comparator;

    public MinHeap(int capacity) {
        this(capacity, null);
    }

    public MinHeap(int capacity, Comparator<E> comparator) {
        if (capacity < 2) {
            throw new IllegalArgumentException();
        }

        this.elements = (E[]) new Object[capacity];

        if (comparator == null) {
            this.comparator = new Comparator<E>() {
                @Override
                public int compare(E o1, E o2) {
                    Comparable<E> c1 = (Comparable<E>) o1;
                    return c1.compareTo(o2);
                }
            };
        } else {
            this.comparator = comparator;
        }
    }

    public void add(E e) {
        if (e == null) {
            throw new NullPointerException();
        }

        this.size += 1;

        if (this.size >= this.elements.length) {
            this.elements = Arrays.copyOf(this.elements, this.elements.length * 2);
        }

        this.elements[this.size] = e;

        //上浮
        int i = this.size;
        int j = i / 2;
        while (j > 0) {
            if (this.comparator.compare(this.elements[j], this.elements[i]) > 0) {
                E tmp = this.elements[i];
                this.elements[i] = this.elements[j];
                this.elements[j] = tmp;
            }

            i = j;
            j = j / 2;
        }
    }

    public E pop() {
        if (this.size < 1) {
            return null;
        }

        E min = this.elements[1];

        this.elements[1] = this.elements[this.size];
        this.elements[this.size--] = null;

        //下沉
        int i = 1;
        int j = 2 * i;
        while (j <= this.size) {
            if (j < this.size) {
                if (this.comparator.compare(this.elements[j], this.elements[j + 1]) < 0) {
                    E tmp = this.elements[i];
                    this.elements[i] = this.elements[j];
                    this.elements[j] = tmp;
                } else {
                    E tmp = this.elements[i];
                    this.elements[i] = this.elements[j + 1];
                    this.elements[j + 1] = tmp;
                    j = j + 1;
                }
            } else {
                if (this.comparator.compare(this.elements[i], this.elements[j]) > 0) {
                    E tmp = this.elements[i];
                    this.elements[i] = this.elements[j];
                    this.elements[j] = tmp;
                }
            }

            i = j;
            j = 2 * j;
        }


        return min;
    }

    @Override
    public String toString() {
        return "MinHeap{" +
                "elements=" + Arrays.toString(elements) +
                ", size=" + size +
                '}';
    }
}
